import java.util.Arrays;
//优先级队列的实现
public class TestHeap {
    private int[] elem;
    private int usedSize;

    public TestHeap() {
        this.elem = new int[10];
    }
    public void initHeap(int[] array){
        for (int i = 0; i < elem.length; i++) {
            elem[i] = array[i];
            usedSize++;
        }
    }
    //最后一个父亲的下标==（数组长度-1（最后一个叶子节点）-1）/2
    //若p是最后一个父亲的下标那么p--就可以把每棵子树调整结束,c用来判断左右孩子的最大值
    //向下调整
    public void creatHeap(){
        for (int parent = (usedSize-1-1) / 2; parent >= 0 ; parent--) {
            shiftDown(parent,usedSize);
        }
    }//当我们采用向下调整去建堆时，时间复杂度O（n）
    private void shiftDown(int parent,int usedSize){
        int child = (2*parent)+1;//左孩子
        //判断左孩子是否合法
        while(child < usedSize){
            if(child+1 < usedSize && elem[child] < elem[child+1]){//右孩子是否合法
                child++;
            }
            //child一定是左右孩子最大值的下标
            if(elem[child] > elem[parent]) {
                swap(child, parent);
                parent = child;
                child = 2*parent+1;
            }else{
                //本身已经是大根堆了
                break;
            }
        }
    }
    private  void swap(int i,int j){
        int tmp = elem[i];
        elem[i] = elem[j];
        elem[j] = tmp;
    }
    //堆的插入（空间不够要扩容）
    //插入和删除都是log2（n）
    public  void offer(int val){
        if(isFull()){
            this.elem = Arrays.copyOf(elem,2*elem.length);
        }
        this.elem[usedSize] = val;//useSize=0
        //向上调整
        shiftUp(usedSize);
       usedSize++;
    }

    private void shiftUp(int child) {
        int parent = (child-1)/2;
        while(child > 0) {
            if (elem[child] > elem[parent]) {
                swap(child,parent);
                child = parent;
                parent = (child-1)/2;
            } else {
                break;
            }
        }
    }

    public boolean isFull(){
        return usedSize == elem.length;
    }
    //删除0下标的元素
    public  int poll(){
        int tmp = elem[0];
        //0下标元素和最后一个元素交换
        swap(0,usedSize-1 );
        //向下调整0~usedsize-1
        usedSize--;//删除
        shiftDown(0,usedSize);
        return tmp;
    }
    //获取堆顶元素
    public int peek(){
        return  this.elem[0];
    }
}
